package com.chengqs.leetcode.hot100;

import com.chengqs.leetcode.utils.DataGeneratorUtil;
import com.chengqs.leetcode.utils.TimeCostUtil;

import java.util.Deque;
import java.util.LinkedList;

/**
 * 双指针<br>
 * 栈、数组、双指针、动态规划、单调栈<br>
 * 困难
 *
 * <h1>42. 接雨水</h1>
 *
 * <p>给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。</p>
 */
public class B07Trap {
    public static void main(String[] args) {
        B07Trap trap = new B07Trap();

        int[] height = {0,1,0,2,1,0,1,3,2,1,2,1};

        TimeCostUtil.timeCost("动态规划", () -> trap.solution1(height));
        TimeCostUtil.timeCost("单调栈", () -> trap.solution2(height));
        TimeCostUtil.timeCost("双指针", () -> trap.solution3_1_mine(height));
        TimeCostUtil.timeCost("双指针_我的方法", () -> trap.solution3_mine(height));
        System.out.println(trap.solution3_1_mine(height));
        System.out.println(trap.solution3(height));

        int[] height2 = DataGeneratorUtil.generateRandomIntArray(10000000, 0, 50);
        TimeCostUtil.timeCost("动态规划", () -> trap.solution1(height2));
        TimeCostUtil.timeCost("单调栈", () -> trap.solution2(height2));
        TimeCostUtil.timeCost("双指针", () -> trap.solution3_1_mine(height2));
        TimeCostUtil.timeCost("双指针_我的方法", () -> trap.solution3_mine(height2));


    }

    public int solution3_mine(int[] height) {
        int l = 0, r = height.length - 1;
        int area = 0;
        int lMax = height[l], rMax = height[r];
        while (l < r) {
            if (lMax <= rMax) {
                area += lMax - height[l];
                l++;
                lMax = Math.max(lMax, height[l]);
            } else {
                area += rMax - height[r];
                r--;
                rMax = Math.max(rMax, height[r]);
            }
        }
        return area;
    }

    // 动态规划
    public int solution1(int[] height) {
        int n = height.length;
        if (n == 0) {
            return 0;
        }

        int[] leftMax = new int[n];
        leftMax[0] = height[0];
        for (int i = 1; i < n; ++i) {
            leftMax[i] = Math.max(leftMax[i - 1], height[i]);
        }

        int[] rightMax = new int[n];
        rightMax[n - 1] = height[n - 1];
        for (int i = n - 2; i >= 0; --i) {
            rightMax[i] = Math.max(rightMax[i + 1], height[i]);
        }

        int ans = 0;
        for (int i = 0; i < n; ++i) {
            ans += Math.min(leftMax[i], rightMax[i]) - height[i];
        }
        return ans;
    }

    // 单调栈
    public int solution2(int[] height) {
        int ans = 0;
        Deque<Integer> stack = new LinkedList<Integer>();

        int n = height.length;
        for (int i = 0; i < n; ++i) {
            while (!stack.isEmpty() && height[i] > height[stack.peek()]) {
                // 如果栈顶的元素小于当前元素，收集这个栈顶元素的雨水
                // 取出栈顶元素
                int top = stack.pop();
                if (stack.isEmpty()) {
                    // 如果为空，说明左边没有比右边更高的元素，停止收集
                    break;
                }
                // 查看栈顶元素左边的元素高度
                int left = stack.peek();
                // 计算当前雨水的面积
                int currWidth = i - left - 1;
                // 计算栈顶元素左右两边的最小值
                int currHeight = Math.min(height[left], height[i]) - height[top];
                // 雨水面积 = 宽度 * 高度
                ans += currWidth * currHeight;
            }
            stack.push(i);
        }
        return ans;
    }

    // 双指针
    public int solution3(int[] height) {
        int ans = 0;
        int left = 0, right = height.length - 1;
        int leftMax = 0, rightMax = 0;
        while (left < right) {
            leftMax = Math.max(leftMax, height[left]);
            rightMax = Math.max(rightMax, height[right]);
            if (height[left] < height[right]) {
                ans += leftMax - height[left];
                ++left;
            } else {
                ans += rightMax - height[right];
                --right;
            }
        }
        return ans;
    }

    public int solution3_1_mine(int[] height) {
        int p1 = 0;
        int p2 = height.length - 1;

        int h = 1;
        int sum = 0;
        while (p1 <= p2) {
            while (height[p1] < h && p1 < p2) p1++;
            while (height[p2] < h && p1 < p2) p2--;
            if (p1 == p2) {
                if (h - height[p1] == 1) {
                    break;
                } else {
                    sum += height[p1] - h;
                }
                sum += p2 - p1 + 1;
            } else if (p1 > p2) {
                break;
            } else {
                sum += p2 - p1 + 1;
            }
            h++;
        }
        int stone = 0;
        for (int i = 0; i < height.length; i++) {
            stone += height[i];
        }
        return sum - stone > 0 ? sum - stone : 0;
    }
}
